class Solution {
public:
    int pivotIndex(vector<int>& nums)
    {
        //1 7 3   6   5   6
        //0 1 2   3   4   5

        //0 1 8 11  17  22  28
        //0 1 2 3   4   5   6
        vector<int> dp(nums.size() + 1, 0);
        for (int i = 1; i <= nums.size(); i++)
            dp[i] = dp[i - 1] + nums[i - 1];

        for (int i = 1; i <= nums.size(); i++)
        {
            if (dp[i] - nums[i - 1] == dp[dp.size() - 1] - dp[i])
                return i - 1;
        }
        return -1;
    }
};